class Solution {
    vector<vector<string>> ret;
    vector<string> path;
    bool isHuiwen(string s) {
        if (s.size() == 1)
            return true;
        for (int i = 0; i < s.size() / 2; i++) {
            if (s[i] != s[s.size() - 1 - i])
                return false;
        }
        return true;
    }

public:
    vector<vector<string>> partition(string s) {
        dfs(s, 0);
        return ret;
    }
    void dfs(const string& s, int start) {
        if (start == s.size()) {
            ret.push_back(path);
            return;
        }
        for (int i = start; i < s.size(); i++) {
            if (isHuiwen(s.substr(start,i-start+1)))
            {
                path.push_back(s.substr(start,i-start+1));
                dfs(s,i+1);
                path.pop_back();
            }
        }
    }

};